Throughout this disclosure (including in the claims), “DFT” denotes a discrete Fourier transform, “FFT” denotes a Fast Fourier Transform (which is a specific type of DFT), “IFFT” denotes an inverse Fast Fourier Transform, “MDCT” denotes the well-known modified discrete cosine transform, and “IDCT” denotes the well-known inverse DCT (inverse modified discrete cosine transform).
Throughout this disclosure (including in the claims) the expression “T/F transform” denotes a time-domain to frequency-domain transform in which time-domain data (e.g., time-domain audio data) are converted to frequency-domain data. Examples of T/F transforms include a DFT and an MDCT.
Throughout this disclosure (including in the claims) the expression “F/T transform” denotes a frequency-domain to time-domain transform (e.g., an inverse T/F transform) in which frequency-domain data (e.g., frequency-domain audio data) are converted to time-domain data. Examples of F/T transforms include an inverse DFT, an inverse MDCT, and an IDCT.
Throughout this disclosure (including in the claims) the expressions “repetitive tasks” and “repetitive actions” denote steps (of data processing operations) that perform the same mathematical operation (or sequence of operations) on each set of operands in a sequence of operand sets. The term “repetitive” is used as a synonym for “iterative.” Examples of repetitive tasks include matrix multiplication and scaling. Repetitive tasks are required in many filtering, scaling, and F/T and T/F transforms, and are often performed on large blocks of data (e.g., audio data).
Throughout this disclosure (including in the claims) the term “comprises” denotes “is” or “includes,” and the expression “in a manner equivalent to” denotes either “by” or “in a manner not identical to but equivalent to.”
In recent years consumer electronic devices employing audio compression have achieved tremendous commercial success. The most popular category of these devices includes the so-called MP3 players and portable media players. Such a player can store user-selected songs in compressed format on a storage medium present in the player, and includes electronic circuitry that decodes and decompresses the compressed songs in real time. Several audio compression formats (e.g., MPEG1-Layers I, II, III, MPEG2-AAC, Windows Media Audio or “WMA,” and Dolby AC3) are in use.
Most conventional audio compression algorithms use a perceptual transform coding paradigm. In perceptual transform coding, a time-domain audio signal is converted to frequency-domain using a T/F transform during encoding. During decoding the reconstructed frequency-domain coefficients are converted to time-domain reconstructed audio samples using an inverse T/F transform.
The T/F transform most commonly used for audio data processing is the Modified Discrete Cosine Transform (MDCT) also referred to as Time-Domain Alias Cancellation (TDAC) filter-bank. For example, Dolby AC3, MPEG2-AAC, and WMA all use MDCT.
The inverse MDCT equations for conversion from frequency-domain coefficients X(k) to time-domain samples x(n), which are typically audio data samples, are:
                                          x            ⁡                          (              n              )                                =                      c            ·                                          ∑                                  k                  =                  0                                                                      N                    /                    2                                    -                  1                                            ⁢                                                          ⁢                                                X                  ⁡                                      (                    k                    )                                                  ·                                  cos                  ⁡                                      (                                                                                            2                          ⁢                          π                                                N                                            ·                                              (                                                  n                          +                                                      n                            0                                                                          )                                            ·                                              (                                                  k                          +                                                      1                            /                            2                                                                          )                                                              )                                                                                      ,                                  ⁢                              for            ⁢                                                  ⁢            n                    =          0                ,        1        ,        …        ⁢                                  ,                  N          -          1.                                    (        1        )            
In case of an inverse MDCT performed to implement MPEG2-AAC decoding, the phase factor n0 in equation (1) satisfies n0=(N/2+1)/2, and the scaling constant c is c=2/N.
It is well known (for example, as described in U.S. Pat. No. 5,890,106) that:
an MDCT can be implemented as three operations on the input time-domain values: pre-modulation followed by a DFT (e.g., an FFT) or DCT (direct cosine transform) to generate transformed data, and finally post-modulation of the transformed data, and
an inverse MDCT can be implemented as three operations on input frequency-domain coefficients X(k): pre-modulation followed by a inverse DFT (e.g., an inverse FFT or “IFFT”) or inverse DCT to generate inverse-transformed data, and finally post-modulation of the inverse-transformed data.
In this disclosure (including in the claims), the expression “intermediate transform” is used to denote the DFT or DCT performed between the pre-modulation and post-modulation phases of an MDCT, or the inverse DFT or inverse DCT performed between the pre-modulation and post-modulation phases of an inverse MDCT.
Thus, it is well known to implement an inverse MDCT by determining time-domain values g(n) in response to frequency coefficients X(k) as follows:g(n)=post-modulation(IFFT(pre-modulation(G(k)),  (2)where Re(G(k))=−X(2k) and Im(G(k))=X(N/2−2k−1) for k=0, . . . , N/4.
The time-domain signal is then derived from Re(g(n)) and Im(g(n)) of equation (2) by index reassignment and sign modifications. The derivation of the decomposition of an inverse MDCT into pre-modulation, inverse FFT, and post-modulation operations and relation between x(n) and g(n) is well known and available in literature.
Since the introduction of the first portable audio players in the market in 1997, MPEG1-Layer III (or “MP3”) audio format has become the de-facto standard for portable media players. The format has been so successful that the term MP3 is sometimes used as a synonym for compressed audio and the expression MP3 player is sometimes used to denote any portable audio player.
In perceptual transform coding, time-domain samples of input audio are first converted into frequency-domain coefficients using an analysis filterbank. The frequency-domain coefficients at the output of analysis filterbank are then quantized using perceptual criteria in order to achieve the highest audio quality at the desired bit rate. At the decoder, the frequency-domain coefficients are reconstructed through the process of inverse quantization of the quantized coefficients. The reconstructed frequency-domain coefficients are then transformed back to time-domain audio samples using a synthesis filterbank.
MPEG1-Layers I, II, and III all use a pseudo perfect-reconstruction quadrature mirror filterbank (QMF) to implement a T/F transform during encoding. Such an analysis filterbank decomposes the time-domain signal to be encoded into 32 streams of frequency coefficients (also referred to as 32 “frequency band signals” or 32 streams of “frequency-band coefficients”), each corresponding to a different one of 32 different frequency bands. The MPEG1-Layer III (“MP3”) encoding method further decomposes each of such 32 frequency sub-band signals into 18 streams of frequency-domain coefficients (which are also “frequency band signals,” each corresponding to a different one of 18 different frequency sub-bands of one of the 32 frequency bands, and are sometimes referred to herein as “frequency sub-band signals” or streams of “frequency sub-band coefficients”) using a modified discrete cosine transform. Thus a 576-band analysis filterbank can be used to convert time-domain samples of input audio into 576 streams of frequency sub-band coefficients (which are then quantized) to implement MP3 encoding.
Another conventional audio compression format is Sub Band Coding (“SBC”). The SBC algorithm also uses a pseudo perfect-reconstruction QMF to implement a T/F transform during SBC encoding. Such an analysis filterbank decomposes the time-domain signal to be encoded into 4 or 8 frequency bands. Thus, a four-band (or eight-band) analysis filterbank can be used to convert time-domain samples of input audio into 4 (or 8) streams of frequency-domain coefficients (which then undergo quantization) to implement SBC encoding.
During conventional encoding (e.g., MP3 or SBC encoding) of audio data of the types discussed above, it is known to implement an analysis filterbank as a first stage configured to perform anti-aliasing (or low-pass) filtering followed by a second stage configured to perform a time-domain to frequency-domain transform (e.g., an MDCT, during MP3 encoding). A cascade of such a first stage and such a second stage is equivalent to (and can implement) a filter stage (that implements any of a broad class of filtering operations) followed by a decimation (down-sampling) stage.
During conventional decoding (e.g., MP3 or SBC decoding) of audio data of the types discussed above, it is known to implement a synthesis filterbank as a first stage configured to perform a frequency-domain to time-domain transform (e.g., an inverse MDCT) followed by a multi-input multi-output low-pass filtering operation. A cascade of such a first stage and such a second stage is equivalent to (and is derived from) an up-sampling stage followed by a filter stage (that implements a bank of parallel band-pass filters that are cosine-modulated versions of a low-pass prototype filter).
Most digital signal-processing algorithms consist of repetitive tasks that are large in scope, and typically produce large dimensional arrays (memory blocks) as outputs in response to large dimensional arrays (memory blocks) as inputs. Conventional digital signal processors typically implement these tasks using a hardware and/or software loop. The loop or nested-loops consist of many instructions. Although this approach provides programmability it is not the most efficient in terms of power consumption, clock cycles or die size.
Above-cited U.S. patent application Ser. No. 11/243,292 discloses systems and methods for performing repetitive tasks (e.g., matrix multiplications and other operations) with improved power and computational efficiency, using a co-processor hardware accelerator that requires small configuration overhead and achieves low-power and high efficiency. However, U.S. application Ser. No. 11/243,292 does not explain how to configure and operate a configurable co-processor to perform an MDCT or inverse MDCT on data (e.g., by pre-modulating the data, performing an intermediate transform on the pre-modulated data, and post-modulating the data generated during the intermediate transform, or in any other way). Nor does it teach how to configure and operate a configurable co-processor to perform efficient matrix multiplication (in which only a subset of the coefficients of a matrix to be multiplied are read from external memory) or efficient alternating addition/subtraction of pairs of operands, or how to configure and operate a configurable co-processor to operate in efficient addressing modes for reading input values (to be operated on by the configured co-processor) from memory or writing output values generated during post-configuration operation of a configured co-processor to memory. It would be desirable to configure and operate a configurable co-processor to perform an MDCT or inverse MDCT on data by pre-modulating the data, performing an intermediate transform on the pre-modulated data, and post-modulating the data generated during the intermediate transform, with high computational efficiency and in a manner consuming low power, and to configure and operate a configurable co-processor efficiently to perform matrix multiplication and/or alternating addition/subtraction on pairs of operands, and/or to implement efficient addressing modes during post-configuration operation.